#include <algorithm>
#include <string>
using namespace std;
class Solution {
    void reverse(string &s, int start, int end) {
        int i=start, j=end;
        while (i<=j) swap(s[i++], s[j--]);
    }
public:
    void reverseWords(string &s) {
        // remove leading and trailing spaces
        int start, end;
        for (start=0;start<s.size() && s[start]==' ';start++);
        for (end=s.size()-1; end>=0 && s[end]==' ';--end);
        if (start==s.size()) s=""; else s=s.substr(start, end-start+1);
        // replace duplicated spaces to single one
        if (s.size()>0) {
            start=0;
            for (end=1;end<s.size();end++)
                if (s[start]!=' ' || s[end]!=' ') s[++start]=s[end];
            s.resize(start+1);
        }
        // reverse each word
        for (int i=-1, j=0; j<s.size(); j++) {
            if (s[j]!=' ' && i==-1) i=j;
            if (i!=-1 && (j==s.size()-1 || s[j+1]==' ')) {
                reverse(s, i, j);
                i = -1;
            }
        }
        // reverse the whole string
        if (s.size()>0) reverse(s, 0, s.size()-1);
    }
};
